package leetcode_jz_offer.day23;

/**
 * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中B[i] 的值是数组 A 中除了下标 i 以外的元素的积
 * 即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
 **/
public class Num66_构建乘积数组 {
    /*方法1：左右乘积列表*/

    /**
     * 当前元素的值=除当前元素以外的元素的乘积=当前元素左边元素的总乘积*当前元素右边元素的总乘积
     * 构建两个新数组left[]+right[]，left[i]存储索引元素左边元素的总乘积，right[i]存储当前元素左边元素的总乘积
     * 对于left数组，left[0]=1,因为第一个元素左边没有元素。其他元素：left[i]=left[i-1]*a[i-1]
     * 对于right数组，right[length-1]=1,因为最后一个元素右边没有元素。其他元素：right[i]=right[i+1]*a[i+1]
     * B[i]存储除当前下标以外的元素的乘积=i下标左侧元素之积*i下标右侧元素之积=left[i]*right[i]
     * @param a
     * @return
     */
    public int[] constructArr(int[] a) {
        int len=a.length;
        int left[]=new int[len];
        int right[]=new int[len];
        int B[]=new int[len];
        if(a==null||a.length==0){
            return B;
        }
        //left[i]
        left[0]=1;
        for (int i = 1; i < len; i++) {
            left[i]=left[i-1]*a[i-1];
        }
        //right[i]
        right[len-1]=1;
        for (int i = len-2; i >= 0; i--) {
            right[i]=right[i+1]*a[i+1];
        }
        //B[i]
        for (int i = 0; i < len; i++) {
            B[i]=left[i]*right[i];
        }
        return B;
    }
    /*方法2：让B[i]直接表示i左侧元素乘积，遍历完左侧后定义一个数动态表示右侧乘积r。上一个方法空间复杂度O(n)，这个O(1)*/
    /**
     * 由于输出数组不算在空间复杂度内，那么我们可以将 L 或 R 数组用输出数组来计算。
     * 先把输出数组当作 L 数组来计算，然后再动态构造 R 数组得到结果。让我们来看看基于这个思想的算法。
     * 算法
     * 初始化 answer 数组，对于给定索引 i，answer[i] 代表的是 i 左侧所有数字的乘积。
     * 构造方式与之前相同，只是我们试图节省空间，先把 answer 作为方法一的 L 数组。
     * 这种方法的唯一变化就是我们没有构造 R 数组。而是用一个遍历来跟踪右边元素的乘积。并更新数组 answer[i]=answer[i]*Ranswer[i]=answer[i]∗R。然后 RR 更新为 R=R*a[i]R=R∗a[i]，其中变量 RR 表示的就是索引右侧数字的乘积。
     */
    public int[] constructArr2(int[] a) {
        //要创建的B数组直接先表示为求左侧元素乘积
        int[] B=new int[a.length];
        if (a==null||a.length==0){
            return B;
        }
        // B[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 B[0] = 1
        B[0]=1;
        for (int i = 1; i < B.length; i++) {
            B[i]=B[i-1]*a[i-1];
        }


        // r 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 r = 1
        int r=1;
        for (int i = B.length-1; i >= 0; i--) {
            B[i]=B[i]*r;//i的左侧元素的积B[i]*右侧元素的乘积r
            // r 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值a[i]乘到 r 上
            r*=a[i];
        }
        return B;
    }
}
